// https://www.lintcode.com/problem/counting-bits/description

class Solution {
public:
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    // 法一：
    // vector<int> countBits(int num) {
    //     vector<int> result;
    //     for (int i = 0; i <= num; ++i)
    //     {
    //         int tmp = 0;
    //         int n = i;
    //         while (n)
    //         {
    //             n = n & (n - 1);
    //             tmp++;
    //         }
    //         cout << tmp << endl;
    //         result.push_back(tmp);
    //     }
    //     return result;
    // }
    
    vector<int> countBits(int num) {
        vector<int> result(num + 1);
        result[0] = 0;
        for (int i = 1; i <= num; ++i)
        {
            // result[num] = result[num >> 2]; 别搞错了，是移一位；又把i搞成num
            // result[i] = result[i >> 1]; 
            // if (i % 2 == 1) result[i]++;
            result[i] = result[i >> 1] + i % 2;
        }
        return result;
    }
};